/*
 * Atomic Predicates for Transformers
 * 
 * Copyright (c) 2015 UNIVERSITY OF TEXAS AUSTIN. All rights reserved. Developed
 * by: HONGKUN YANG and SIMON S. LAM http://www.cs.utexas.edu/users/lam/NRL/
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * with the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * 1. Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimers.
 * 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimers in the documentation
 * and/or other materials provided with the distribution.
 * 
 * 3. Neither the name of the UNIVERSITY OF TEXAS AUSTIN nor the names of the
 * developers may be used to endorse or promote products derived from this
 * Software without specific prior written permission.
 * 
 * 4. Any report or paper describing results derived from using any part of this
 * Software must cite the following publication of the developers: Hongkun Yang
 * and Simon S. Lam, Scalable Verification of Networks With Packet Transformers
 * Using Atomic Predicates, IEEE/ACM Transactions on Networking, October 2017,
 * Volume 25, No. 5, pages 2900-2915 (first published as IEEE Early Access
 * Article, July 2017, Digital Object Identifier: 10.1109/TNET.2017.2720172).
 * 
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH
 * THE SOFTWARE.
 */
package transformer;

import java.util.ArrayList;

import common.BDDACLWrapper;
import common.ForwardingRule;

/**
 * assume that in one forwarding table, there are no two forwarding rules with the same prefix and port.
 * @author yanghk
 *
 */
public class PrefixTreeNode {

    public final static int sibling = 2;
    public final static int descendant = 1;
    public final static int identical = 0;
    public final static int ancestor = -1;

    static BDDACLWrapper bddengine;

    public final static int bit_num = ForwardingRule.bit_num;
    
    long prefix;
    int prefixlen;
    int prefixbdd;
    ArrayList<String> ports;
    int effectivebdd;
    ArrayList<PrefixTreeNode> children;
    PrefixTreeNode parent;

    public int getprefixlen()
    {
        return prefixlen;
    }
    
    public PrefixTreeNode(ForwardingRule rule) {
        
        this();
        
        this.prefix = rule.getdestip();
        this.prefixlen = rule.getprefixlen();
        this.prefixbdd = bddengine.encodeDstIPPrefix(prefix, prefixlen);
        
        ports.add(rule.getiname());
        
    }
    
    public PrefixTreeNode(ForwardingRule rule, ArrayList<PrefixTreeNode> children)
    {
        this(rule);
        this.children.addAll(children);
    }
    
    public PrefixTreeNode(ForwardingRule rule, PrefixTreeNode parent)
    {
        this(rule);
        this.parent = parent;
    }
    
    public PrefixTreeNode(ForwardingRule rule, ArrayList<PrefixTreeNode> children, PrefixTreeNode parent )
    {
        this(rule, children);
        this.parent = parent;
    }
    
    public void setParent(PrefixTreeNode parent)
    {
        this.parent = parent;
    }
    
    public void addChildren(ArrayList<PrefixTreeNode>new_children)
    {
        children.addAll(new_children);
    }
    
    public void removeChild(PrefixTreeNode child)
    {
        children.remove(child);
    }
    
    /**
     * default routes
     */
    public PrefixTreeNode()
    {
        prefix = 0;
        prefixlen = 0;
        prefixbdd = BDDACLWrapper.BDDTrue;
        effectivebdd = BDDACLWrapper.BDDTrue;
        
        ports = new ArrayList<String> ();
        
        children = new ArrayList<PrefixTreeNode> ();
    }
    
    /**
     * only used by root node
     * @return true: no default rule
     */
    public boolean defaultNotSet()
    {
        return ports.isEmpty();
    }
    
    public void addPort(String newInterface)
    {
        ports.add(newInterface);
    }
    
    public void removePort(String port)
    {
        ports.remove(port);
    }
    
    



    /**
     * assume the root stores prefix 0/0
     * @param newrule
     */
    public PrefixTreeNode insert_to_tree(ForwardingRule newrule)
    {
        ArrayList<PrefixTreeNode> new_children = new ArrayList<PrefixTreeNode> ();

        for(PrefixTreeNode child : children)
        {
            int res = child.compare(newrule);
            //System.out.println(res);
            switch(res)
            {
            case sibling: // do nothing;
                break;
            case identical: // prefix of the newrule is identical to the current node, do not
                                    // need to do other things
                child.addPort(newrule.getiname());
                return child;
            case ancestor: new_children.add(child);
                break;
            case descendant: // go to this child
                return child.insert_to_tree(newrule);
            }
        }
        
        // if reach here, new_rule is a direct child of current node
        PrefixTreeNode new_node = new PrefixTreeNode(newrule, new_children, this);
        
        children.removeAll(new_children);
        for(PrefixTreeNode child : new_children)
        {
            child.setParent(new_node);
        }
        
        children.add(new_node);
        
        // update effective bdd
        new_node.effectivebdd = bddengine.and(new_node.prefixbdd, effectivebdd);
        effectivebdd = bddengine.diffTo(effectivebdd, new_node.prefixbdd);
        
        return new_node;

    }
    
    // search based on prefix only
    public PrefixTreeNode search(ForwardingRule rule)
    {
        for(PrefixTreeNode child : children)
        {
            int res = child.compare(rule);
            //System.out.println(res);
            switch(res)
            {
            case sibling: // do nothing;
                break;
            case identical: // got it
                return child;
            case ancestor: // do nothing
                break;
            case descendant: // go to this child
                return child.search(rule);
            }
        }
        
        return null;
    }
    
    public String getEffectivePort()
    {
        return ports.get(0);
    }
    
    /**
     * when ports is empty, the node should be removed, except that it is the root
     * @return
     */
    public boolean isInvalid()
    {
        return ports.isEmpty();
    }
    
    
    /**
     * delete current node
     * return parent
     */
    public PrefixTreeNode delete_from_tree()
    {
        PrefixTreeNode parent = this.parent;
        parent.removeChild(this);
        parent.addChildren(children);
        for (PrefixTreeNode child : children)
        {
            child.setParent(parent);
        }
        
        this.parent = null;
        this.children.clear();
        
        return parent;
    }

    public void traverse()
    {
        System.out.println(toString());
        if(children.isEmpty())
        {
            System.out.println("+++");
        }else
        {
            for(PrefixTreeNode node : children)
            {
                node.traverse();
            }
        }
    }
    
    public void reverse()
    {
        System.out.println(toString());
        if(parent != null)
        {
            parent.reverse();
        }
    }

    public String toString()
    {
        return prefix+" " + prefixlen + " " + ports;
    }

    /**
     * 
     */
    public int compare(ForwardingRule newrule)
    {
        int len1 = prefixlen;
        int len2 = newrule.getprefixlen();
        int minlen = len1;
        if(minlen > len2)
        {
            minlen = len2;
        }
        long val1 = prefix >> (ForwardingRule.bit_num - minlen);
        long val2 = newrule.getdestip() >> (ForwardingRule.bit_num - minlen);

        if(val1 != val2)
        {
            return sibling;
        }else
        {
            if(len1 < len2)
            {
                return descendant;
            }else if(len1 > len2)
            {
                return ancestor;
            }else
            {
                return identical;
            }
        }
    }

    public static void main (String[] args)
    {
        /**
         * do some test
         */
        PrefixTreeNode.bddengine = new BDDACLWrapper();
        PrefixTreeNode root = new PrefixTreeNode();
        root.addPort("1");
        PrefixTreeNode n1 = root.insert_to_tree(new ForwardingRule(0,30,"2"));
        PrefixTreeNode n2 = root.insert_to_tree(new ForwardingRule(8,30,"2"));
        PrefixTreeNode n3 = root.insert_to_tree(new ForwardingRule(12,30, "3"));
        PrefixTreeNode n4 = root.insert_to_tree(new ForwardingRule(2,31,"3"));
        PrefixTreeNode n5 = root.insert_to_tree(new ForwardingRule(0,31,"1"));
        PrefixTreeNode n6 = root.insert_to_tree(new ForwardingRule(0,31, "2"));
        PrefixTreeNode n7 = root.insert_to_tree(new ForwardingRule(12,30,"1"));
        
        String separator = "----------";
        System.out.println(separator);
        root.traverse();
        System.out.println(separator);
        
        PrefixTreeNode n8 = root.search(new ForwardingRule(12, 30, null));
        System.out.println(n8);
        System.out.println(n8.getEffectivePort());
        n8.removePort("3");
        System.out.println(n8.getEffectivePort());
        n8.removePort("1");
        System.out.println(n8.isInvalid());

        //n4.reverse();
        //System.out.println(separator);
        //n5.reverse();
        //System.out.println(separator);
        
        //n1.delete_from_tree();
        //root.traverse();
        //System.out.println(separator);
        //root.insert_to_tree(new ForwardingRule(n1.prefix, n1.prefixlen, n1.ports.get(0)));
        //root.traverse();
        //System.out.println(separator);
        
    }

}
